Skip to main content

Generalized Abbreviation

Question​

com

What is the most efficient algorithm for generating all the possible valid abbreviations of a given word?

Example 1
Input: "word"

Output: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Solution​

all//Generalized Abbreviation.py


def general_abbreviation(word):
    n = len(word)
    result = []
    for i in range(1<<n):
        temp = []
        for j in range(n):
            if (i & (1<<j)) != 0:
                temp.append(word[j])
            else:
                if len(temp) > 0:
                    temp.append(str(len(temp)))
                    result.append("".join(temp))
                    temp = []
        if len(temp) > 0:
            temp.append(str(len(temp)))
            result.append("".join(temp))
    return result

print(general_abbreviation("word"))
# ['w1d', 'wo1', 'w2', 'wr1', 'word']